English
Zadanie Podzbiory [A] (pod)
Subsets [A]
Memory limit: 32 MB
We are going to consider subsets 
of a given set 
.
We are interested in subsets such that for a given natural number 
and for
any natural number 
at least one of the numbers 
, 
doesn't belong to 
.
We would like to calculate the number of such subsets, that have exactly 
elements.
It is possible that the number of such subsets is huge - therefore it is sufficient to calculate the remainder of the division
of the result by 
.
Task
Write a program which:
- reads from the standard input four integers:
, 
, 
and 
,
- calculates the remainder of the division by
of the number of 
-element subsets of set 
, that fulfill
the requirements described above,
- writes result to the standard output.
Input
In the first and only line of the standard input there are four integers 
, 
, 
and 
(
,
, 
,
), separated by single spaces.
Output
The first and only line should contain one integer - the reminder of the division by 
of the number of 
-element subsets
of set 
that fulfill the specified requirements.
Example
For the input data:
6 1234 3 2
the correct result is:
9
Considered subsets are:
,
,
,
,
,
,
,
and
.
Task author: Jakub Radoszewski.